//WRITE END STATES FOR NFA'S!!!!!!!!!!!!!!!!!!!!!!!!!

package token;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import character.CharSpec;
import character.Input;
import character.NFA;
import character.State;


public class Parser {
	
	Stack<NFA> containmentStack = new Stack<NFA>();
	NFA currentNFA = new NFA();
	
	private character.Parser charParser;
	private String regEx = "";
	private int cursor = 0;
	private int stateNum = 0;
	
	
	final private String RE_CHAR = "!#$%&,-/0123456789:;<=>@ABCDEFGHIJKLMNOPQRSTUVWXYZ^_`abcdefghijklmnopqrstuvwxyz{}~";
	final private String CLS_CHAR = "!\"#$%&'()*+,./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ_`abcdefghijklmnopqrstuvwxyz{|}~";
	
	/**
	 * Simple helper function for removing substrings from a string and shifting the
	 * remaining characters
	 * @param s
	 * @param beginIndex
	 * @param endIndex
	 * @return
	 */
	public static String removeSubString(String s, int beginIndex, int endIndex) {
		StringBuffer sb = new StringBuffer(s.length());
		sb.setLength(s.length());
		sb.replace(beginIndex, endIndex, "");
		return sb.toString();
	}
	/**
	 * Simple helper function for replacing substrings with new strings
	 * @param s
	 * @param beginIndex
	 * @param endIndex
	 * @param replace
	 * @return
	 */
	public static String replaceSubString(String s, int beginIndex, int endIndex, String replace) {
		StringBuffer sb = new StringBuffer(s.length());
		sb.setLength(s.length());
		sb.replace(beginIndex, endIndex, replace);
		return sb.toString();
	}
	
	
	/**
	 * The constructor for the token definition parser 
	 */
	public Parser(character.Parser charParser) {
		this.charParser = charParser;
	}
	/**
	 * This method deals with parsing a single line in the token definition section of the input
	 * definition file (e.g. $IDENTIFIER     	$SMALLCASE ($LETTER | $DIGIT)*)
	 * It begins by pulling out the token's title and regex first, isolating them, and then makes the
	 * proper method calls to create a token specification with an NFA as a representation
	 */
	public NFATokenSpec parseLine(String line) {
//		String titleString = "";
//		int regExBegin = 0;
//		int titleEnd = line.indexOf(' ');
//		for (int i = titleEnd; i < line.length(); i++) {
//			if (line.charAt(i) != ' ') {
//				regExBegin = i;
//				break;
//			}
//		}
//		titleString = line.substring(0, regExBegin - 1);
//		titleString = titleString.trim();
		NFATokenSpec newSpec = new NFATokenSpec("");
		
		String regEx = line;
		regEx = regEx.trim();
		this.regEx = regEx;
		parseRegEx(regEx);
		newSpec.setRepresentative(currentNFA);
		
		containmentStack = new Stack<NFA>();
		currentNFA = new NFA();
		return newSpec;
	}
	
	
	
	/**
	 * The opening method call for the recursive descent parser, with the general grammar defined in the
	 * appendix of the file given in the assignment.  A stack is used to maintain the multiple NFA's
	 * produced over the course of parsing the regEx, as well as a cursor to point to the current
	 * token being parsed.
	 * @param regEx The full regEx passed into the parser, although the private instance variable is
	 * referenced as well
	 */
	public void parseRegEx(String regEx) {
		
		rexp();
		cursor = 0;
		stateNum = 0;
		regEx = "";
		
		

		
	}
	
	public void rexp() {
		currentNFA = new NFA();
		containmentStack.push(currentNFA);
		State startState = new State(stateNum++, new ArrayList<Input>());
		startState.setStartState(true);
		startState.setFinishState(true);
		currentNFA.addState(startState);
		
		rexp1();
		rexpprime();
	
	}

	public void rexpprime() {
		if (peekToken().equals("|")) {
			matchToken("|");
			rexp1();
			rexpprime();
			NFA firstNFA = containmentStack.pop();
			NFA secondNFA = containmentStack.pop();
			NFA finalNFA = NFA.mergeUnion(firstNFA, secondNFA);
			currentNFA = finalNFA;
			containmentStack.push(finalNFA);
		} else {
			return;
		}
	}
	
	public void rexp1() {
		rexp2();
		rexp1prime();
	}
	
	public void rexp1prime() {
		if (peekToken().equals("(") ||
				RE_CHAR.contains(peekToken()) ||
				peekToken().equals("\\ ") ||
				peekToken().equals("\\\\") ||
				peekToken().equals("\\*") ||
				peekToken().equals("\\+") ||
				peekToken().equals("\\?") ||
				peekToken().equals("\\|") ||
				peekToken().equals("\\]") ||
				peekToken().equals("\\[") ||
				peekToken().equals("\\(") ||
				peekToken().equals("\\)") ||
				peekToken().equals("\\.") ||
				peekToken().equals("\\'") ||
				peekToken().equals("\\\"") ||
				peekToken().equals(".") ||
				peekToken().equals("[") ||
				peekToken().equals("DEFINED_CLASS")) {
			rexp2();
			rexp1prime();
		} else {
			return;
		}
	}
	public void rexp2() {
		if (peekToken().equals("(")) {
			matchToken("(");
			rexp();
			matchToken(")");
			rexp2tail();
			
		} else if (RE_CHAR.contains(peekToken()) ||
				peekToken().equals("\\ ") ||
				peekToken().equals("\\\\") ||
				peekToken().equals("\\*") ||
				peekToken().equals("\\+") ||
				peekToken().equals("\\?") ||
				peekToken().equals("\\|") ||
				peekToken().equals("\\]") ||
				peekToken().equals("\\[") ||
				peekToken().equals("\\(") ||
				peekToken().equals("\\)") ||
				peekToken().equals("\\.") ||
				peekToken().equals("\\'") ||
				peekToken().equals("\\\"")) {
				
			matchToken("RE_CHAR");
			rexp2tail();
		} else {
			rexp3();
			NFA smallerNFA = containmentStack.pop();
			NFA largerNFA = containmentStack.pop();
			smallerNFA.getState(stateNum-1).setFinishState(true);
			largerNFA = NFA.mergeConcat(largerNFA, smallerNFA);
			currentNFA = largerNFA;
			containmentStack.push(largerNFA);
			
		}
	}
	
	
	
	public void rexp2tail() {
		if (peekToken().equals("*")) {
			matchToken("*");
		} else if (peekToken().equals("+")) {
			matchToken("+");
		} else {
			NFA smallerNFA = containmentStack.pop();
			NFA largerNFA = containmentStack.pop();
			smallerNFA.getState(stateNum-1).setFinishState(true);
			largerNFA = NFA.mergeConcat(largerNFA, smallerNFA);
			currentNFA = largerNFA;
			containmentStack.push(largerNFA);
			return;
		}
	}
	
	public void rexp3() {
		NFA smallerNFA = new NFA();
		currentNFA = smallerNFA;
		State startState = new State(stateNum++, new ArrayList<Input>());
		startState.setStartState(true);
		smallerNFA.addState(startState);
		containmentStack.push(smallerNFA);
		if (peekToken().equals(".") ||
				peekToken().equals("[") ||
				peekToken().equals("DEFINED_CLASS")) {
				charclass();
		} else {
			return;
		}
	}
	
	public void charclass() {
		if (peekToken().equals(".")) {
			matchToken(".");
		} else if (peekToken().equals("[")) {
			matchToken("[");
			charclass1();
			
		} else {
			matchToken("DEFINED_CLASS");
		}
	}
	public void charclass1() {
//		if (peekToken().equals("CLS_CHAR") ||
//				peekToken().equals("]")) {
		if (CLS_CHAR.contains(peekToken()) ||
				peekToken().equals("\\\\") ||
				peekToken().equals("\\^") ||
				peekToken().equals("\\-") ||
				peekToken().equals("\\[") ||
				peekToken().equals("\\]") ||
				peekToken().equals("]")) {
			charsetlist();
		} else {
			excludeset();
		}
	}
	
	public void charsetlist() {
		if (CLS_CHAR.contains(peekToken()) ||
				peekToken().equals("\\\\") ||
				peekToken().equals("\\^") ||
				peekToken().equals("\\-") ||
				peekToken().equals("\\[") ||
				peekToken().equals("\\]")) {
			charset();
			charsetlist();
		} else {
			matchToken("]");
		}
	}
	public void excludeset() {
		matchToken("^");
		charset();
		matchToken("]");
		matchToken("IN");
		excludesettail();
	}
	
	public void charset() {
		matchToken("CLS_CHAR");
		charsettail();
	}
	
	public void charsettail() {
		if(peekToken().equals("-")) {
			matchToken("-"); //match token for the second CLS_CHAR occurs in this method call
		} else {
			return;
		}
	}
	
	public void excludesettail() {
		if (peekToken().equals("[")) {
			matchToken("[");
			charset();
			matchToken("]");
			
			
			
			State startState = null;
			for (State s : currentNFA.getStates()) {
				if (s.isStartState()) {
					startState = s;
					break;
				}
			}
			State finalState = currentNFA.getState(stateNum-2);
			State excludeState = currentNFA.getState(stateNum-1);
			List<Input> excludeSet = startState.getInputs();
			List<Input> fromSet = currentNFA.getState(stateNum - 2).getInputs();
			finalState.setInputs(new ArrayList<Input>());
			currentNFA.removeState(stateNum-1);
			stateNum--;
			List<Input> newList = new ArrayList<Input>();
			for (Input i : fromSet) {
				boolean isExcluded = false;
				for (Input j : excludeSet) {
					if (i.getTitle().equals(j.getTitle())) {
						isExcluded = true;
					}
				}
				if (isExcluded) {
					continue;
				} else {
					newList.add(i);
				}
			}
			startState.setInputs(newList);
			
		} else {
			matchToken("DEFINED_CLASS");
			
			State startState = null;
			for (State s : currentNFA.getStates()) {
				if (s.isStartState()) {
					startState = s;
					break;
				}
			}
			State finalState = currentNFA.getState(stateNum-2);
			State excludeState = currentNFA.getState(stateNum-1);
			List<Input> excludeSet = startState.getInputs();
			List<Input> fromSet = currentNFA.getState(stateNum - 2).getInputs();
			finalState.setInputs(new ArrayList<Input>());
			currentNFA.removeState(stateNum-1);
			stateNum--;
			List<Input> newList = new ArrayList<Input>();
			for (Input i : fromSet) {
				boolean isExcluded = false;
				for (Input j : excludeSet) {
					if (i.getTitle().equals(j.getTitle())) {
						isExcluded = true;
					}
				}
				if (isExcluded) {
					continue;
				} else {
					newList.add(i);
				}
			}
			startState.setInputs(newList);
		}
	}
	
	

	
	public String peekToken() {
		if (cursor == regEx.length()) {
			return "END";
		}
		char c = regEx.charAt(cursor);
		if (c == '(') {
			return "(";
		}
		if (c == '$') {
			return "DEFINED_CLASS";
		}
		if (Character.toString(c) == "") {
			return "EMPTY";
		}
		if (c == ')') {
			return ")";
		}
		if (c == '[') {
			return "[";
		}
		if (c == ']') {
			return "]";
		}
		if (c == '+') {
			return "+";
		}
		if (c == '*') {
			return "*";
		}
		if (c == '.') {
			return ".";
		}
		if (c == '|') {
			return "|";
		}
		if (c == '-') {
			return "-";
		}
		if (CLS_CHAR.contains(Character.toString(c))) {
			return Character.toString(c);
		}
		if (RE_CHAR.contains(Character.toString(c))) {
			return Character.toString(c);
		}
		if (c == '\\') {
			return Character.toString(c) + 
					Character.toString(regEx.charAt(cursor + 1));
		}
		cursor++;
		return peekToken();
	}
	
	public void matchToken(String token) {
		if (token.equals(")")) {
			cursor++;
		}
		if (token.equals("(")) {
			cursor++;
		}
		if (token.equals("*")) {
			NFA smallerNFA = containmentStack.pop();
			NFA largerNFA = containmentStack.pop();
			smallerNFA.getState(stateNum-1).setFinishState(true);
			smallerNFA = NFA.mergeStar(smallerNFA);
			largerNFA = NFA.mergeConcat(largerNFA, smallerNFA);
			currentNFA = largerNFA;
			containmentStack.push(largerNFA);
			cursor++;
		}
		if (token.equals("+")) {
			NFA smallerNFA = containmentStack.pop();
			NFA largerNFA = containmentStack.pop();
			smallerNFA.getState(stateNum-1).setFinishState(true);
			smallerNFA = NFA.mergePlus(smallerNFA);
			largerNFA = NFA.mergeConcat(largerNFA, smallerNFA);
			currentNFA = largerNFA;
			containmentStack.push(largerNFA);
			cursor++;
		}
		
		if (token.equals("RE_CHAR")) {
			NFA newNFA = new NFA();
			State startState = new State(stateNum++, new ArrayList<Input>());
			startState.setStartState(true);
			newNFA.addState(startState);
			currentNFA = newNFA;
			containmentStack.push(newNFA);
			if (regEx.charAt(cursor) == '\\') {
				State newState = new State(stateNum++, new ArrayList<Input>());
				startState.addInput(new Input(Character.toString(regEx.charAt(cursor))+Character.toString(regEx.charAt(cursor+1)), newState));
				currentNFA.addState(newState);
				cursor = cursor + 2;
			} else {
				State newState = new State(stateNum++, new ArrayList<Input>());
				startState.addInput(new Input(Character.toString(regEx.charAt(cursor)), newState));
				currentNFA.addState(newState);
				cursor++;
			}
		}
		if (token.equals("|")) {
			NFA newNFA = new NFA();
			currentNFA = newNFA;
			containmentStack.push(newNFA);
			State startState = new State(stateNum++, new ArrayList<Input>());
			startState.setStartState(true);
			startState.setFinishState(true);
			newNFA.addState(startState);
			cursor++;
		}
		if (token.equals(".")) {
			State startState = null;
			State newState = new State(stateNum++, new ArrayList<Input>());
			currentNFA.addState(newState);
			for (State s : currentNFA.getStates()) {
				if (s.isStartState()) {
					startState = s;
					break;
				}
			}
			for (int i = 32; i < 126; i++) {
				Input newInput = new Input(Character.toString((char) i), newState);
				startState.addInput(newInput);
			}
			cursor++;
		}
		if (token.equals("DEFINED_CLASS")) {
			CharSpec definedSpec = null;
			String tokenName = "";
			char probe = regEx.charAt(cursor);
			while (probe != '[' &&
					probe != ']' &&
					probe != '(' &&
					probe != ')' &&
					probe != ' ' &&
					probe != '|' &&
					probe != '^' &&
					probe != '\\' &&
					probe != '*' &&
					probe != '+' &&
					probe != '?' &&
					probe != '.' &&
					probe != '\'' &&
					probe != '"') {
				tokenName += Character.toString(probe);
				cursor++;
				probe = regEx.charAt(cursor);
			}
			for (CharSpec spec : charParser.getSpecList()) {
				if (spec.getTitle().equals(tokenName)) {
					definedSpec = spec;
					break;
				}
			}
			State startState = currentNFA.getState(stateNum-1);
			State newState = new State(stateNum++, new ArrayList<Input>());
			currentNFA.addState(newState);
//			for (State s : currentNFA.getStates()) {
//				if (s.isStartState()) {
//					startState = s;
//					break;
//				}
//			}
			for (Character c : definedSpec.getCharList()) {
				Input newInput = new Input(Character.toString(c), newState);
				startState.addInput(newInput);
			}
		}
		if (token.equals("[")) {
			cursor++;
		}
		if (token.equals("]")) {
			cursor++;
		}
		if (token.equals("CLS_CHAR")) {
			State startState = currentNFA.getState(stateNum-1);
			State newState = new State(stateNum++, new ArrayList<Input>());
			currentNFA.addState(newState);
			if (regEx.charAt(cursor) == '\\') {
				startState.addInput(new Input(Character.toString(regEx.charAt(cursor))+Character.toString(regEx.charAt(cursor+1)), newState));
				cursor = cursor + 2;
			} else {
				startState.addInput(new Input(Character.toString(regEx.charAt(cursor)), newState));
				cursor++;
			}
		}
		if (token.equals("-")) {
			State startState = currentNFA.getState(stateNum-2);
			State newState = currentNFA.getState(stateNum-1);
			int beginRange = (int) regEx.charAt(cursor-1);
			int endRange = (int) regEx.charAt(cursor+1);
			beginRange++;
			for (int i = beginRange; i <= endRange; i++) {
				Input newInput = new Input(Character.toString((char) i), newState);
				startState.addInput(newInput);
			}
			cursor = cursor + 2;
		}
		if (token.equals("^")) {
			cursor++;
		}
		if (token.equals("IN")) {
			cursor = cursor + 4;
		}
	}
	

}


	
